﻿#define  _CRT_SECURE_NO_WARNINGS
//给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历，
//postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
struct TreeNode* BuyNode(int x)
{
    struct TreeNode* newnode = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    if (newnode == NULL)
    {
        perror("malloc fail");
    }
    newnode->val = x;
    newnode->right = NULL;
    newnode->left = NULL;

    return newnode;
}

struct TreeNode* buildTree(int* inorder, int inorderSize, int* postorder, int postorderSize) {
    if (postorderSize == 0)
    {
        return NULL;
    }

    struct TreeNode* root = BuyNode(postorder[postorderSize - 1]);

    int i = 0;

    for (i = 0;i < inorderSize;i++)
    {
        if (inorder[i] == postorder[postorderSize - 1])
            break;
    }
    root->left = buildTree(inorder, i, postorder, i);
    root->right = buildTree(inorder + i + 1, inorderSize - i - 1, postorder + i, postorderSize - i - 1);
    return root;
}

